<?php

class SortClass
{
    /*选择排序
     * 1、每一次选择所排序的序列当中最小的一个
     * 2、依次把最小的放到当前排序序列最左
     * 3、记录下最小的原来的位置，和当前序列最左的交换
     * 4、从当前序列最左的下一个开始为下一个排序序列
     */
    public function selectionSort($selectionSort)
    {
        for ($i = 0; $i < count($selectionSort); $i++) {
            $index = $i; ///最小值下标
            $mix   = $selectionSort[$i];
            for ($j = $i + 1; $j < count($selectionSort); $j++) {
                if ($mix > $selectionSort[$j]) {
                    $mix   = $selectionSort[$j];
                    $index = $j; //最小值为j的位置，改变下标的值
                }
            }
            //最小值交换位置
            $temp                  = $selectionSort[$i];
            $selectionSort[$i]     = $selectionSort[$index];
            $selectionSort[$index] = $temp;

        }
        return $selectionSort;
    }
    /*
     * 冒泡排序
     * 1、临近数字进行两两的比较
     * 2、按从小到大的顺序，按比较结果交换
     * 3、依次从左往右比较为一趟
     * 4、重复进行趟的比较 （嵌套循环 外循环控制趟，内循环控制临近数的比较）
     */
    public function bubleSort($bubleSort)
    {
        for ($i = 0; $i < count($bubleSort); $i++) {
            for ($j = $i; $j < count($bubleSort); $j++) {
                if ($bubleSort[$i] > $bubleSort[$j]) {
                    $temp          = $bubleSort[$i];
                    $bubleSort[$i] = $bubleSort[$j];
                    $bubleSort[$j] = $temp;
                }
            }
        }
        return $bubleSort;
    }
    /* 插入排序
     * 理想状态下，将新的数据插入的序列是有序序列
     * 1、从最左开始，将第一个数当做有序序列，从第二个开始排序
     * 2、第二个数从第一个数开始逐个比较，若大则插入比较数的右边
     * 3、对后面的数逐个进行1、2操作
     **/
    public function insertionSort($insertionSort)
    {for ($i = 1; $i < count($insertionSort); $i++) {
        $temp = $insertionSort[$i];
        for ($j = $i - 1; $j >= 0; $j--) {
            if ($insertionSort[$j] > $temp) {
                $insertionSort[$j + 1] = $insertionSort[$j];
                $insertionSort[$j]     = $temp;
            } else {
                break;
            }
        }
    }
        return $insertionSort;
    }

    /* 快速排序
     * 1、选择一个基准
     * 2、小于基准的元素放到左边，大于基准的数放到右边
     * 3、对基准左右两边的数，重复1，递归排序
     * 4、最后合并
     */
    public function quickSort($quick)
    {
        if (count($quick) <= 1) {
            return $quick;
        }
        // 把第一个元素作为基准
        $pivot      = $quick[0];
        $quickLeft  = array();
        $quickRight = array();
        for ($i = 1; $i < count($quick); $i++) {
            if ($quick[$i] < $pivot) {
                $quickLeft[] = $quick[$i];
            } else {
                $quickRight[] = $quick[$i];
            }
        }
        $quickLeft  = SortClass::quickSort($quickLeft);
        $quickRight = SortClass::quickSort($quickRight);
        return array_merge($quickLeft, array(
            $pivot,
        ), $quickRight);
    }
    public function output($output)
    {
        foreach ($output as $num) {
            echo $num;
        }
        echo "<br>";
    }
}
